#include<stdio.h>
#include<stdlib.h>

void merge(int *a,int t,int r)
{
    int k = (t + r)/2;
    int m = k-t+1;
    int n = r-k;
    int *L = malloc(sizeof(int)*(m+1));
    int *G = malloc(sizeof(int)*(n+1));
    int i = 0;
    for(i = 0;i < m;i++)
        {
            L[i] = a[t+i];

        }
    for(i = 0;i < n;i++)
        {
            G[i] = a[k+1+i];
        }

     L[m] = 10000;
     G[n] = 10000;
     int len =r - t + 1;
     int j,p;
     j=0;
     p=0;

     for(i=0;i < len;i++)
        {
           if(L[j] < G[p])
            {
                if(j == m)
                    break;
                a[t+i] = L[j];
                j++;
            }else{
                if(p==n)
                    break;
                a[t+i] = G[p];
                p++;
            }
        }
}

void mergeSort(int *a,int t,int r)
{
    if(t < r){
    int b = (t+r)/2;
    mergeSort(a,t,(t+r)/2);
    mergeSort(a,(t+r)/2+1,r);
    merge(a,t,r);
    }
}

int main()
{
    int a[11] = {2,6,9,4,3,7,1,1,8,0,5};
    mergeSort(a,0,10);
    int i = 0;
    for(i = 0;i < 11;i++)
       printf("%d ",a[i]);
    return 0;
}
